<!doctype html>
<html lang="zh_cn" itemscope itemtype="http://schema.org/Person">
<head>
            <meta charset="utf-8">
        <!-- Site Meta Data -->
        <title>KMP算法之next数组求解说明</title>
        <meta name="viewport" content="width=device-width, initial-scale=1">
        <meta name="description" content="技术博客,涉及Java/PHP/Python/Javascript等,聊聊程序,聊聊生活,聊聊事实,聊聊育儿">
        <meta name="keywords" content="编码经验,技术分享,生活积累,实事评说">
        <meta name="author" content="布丁缘">

        <link rel="shortcut icon" href="">

        <link href='https://fonts.googleapis.com/css?family=Open+Sans:400,600,700' rel='stylesheet' type='text/css'>
        <!-- Style Meta Data -->
        <link rel="stylesheet" href="https://www.ddkiss.com/theme/css/style.css" type="text/css"/>
        <link rel="stylesheet" href="https://www.ddkiss.com/theme/css/pygments.css" type="text/css"/>

        <!-- Feed Meta Data -->
            <link href="https://www.ddkiss.com/feeds/all.atom.xml" type="application/atom+xml" rel="alternate"
                  title="一个程序员的简单生活 ATOM Feed"/>


    <meta name="keywords" content="">
    <link rel="stylesheet" href="//dn-coding-net-public-file.qbox.me/Coding-Comments/v0.1.0/default.css">
</head>

<body>
<!-- Sidebar -->
<aside>
    <center><h1><a href="/" style="color:#fff"><img id="avatar" src="/images/avatar.jpg"></a></h1></center>
        <p>一个程序员的简单生活</p>
    <br>
    <nav class="nav">
        <ul class="list-bare">
                <li><a class="nav__link" href="https://www.ddkiss.com/category/chang-yong-ji-qiao.html">常用技巧</a></li>
                <li><a class="nav__link" href="https://www.ddkiss.com/category/kai-fa-huan-jing.html">开发环境</a></li>
                <li><a class="nav__link" href="https://www.ddkiss.com/category/sheng-huo-dian-di.html">生活点滴</a></li>

                <li><a class="nav__link" href="/pages/books.html">书单</a></li>
                <li><a class="nav__link" href="/pages/movies.html">影单</a></li>
                <li><a class="nav__link" href="/pages/downloads.html">下载</a></li>
                <li><a class="nav__link" href="/pages/about.html">关于我</a></li>


        </ul>
    </nav>


    <form>
      <input type="text"  id="bdcsMain"/>
    </form>

</aside>

<!-- Content -->
<article>
  <main>
    <nav>
      <a href="/">首页</a>
      <a href="/archives.html">归档</a>
      <a href="/categories.html">分类</a>
      <a href="/tags.html">标签</a>
      <a href="/pages/about.html">关于我</a>
    </nav>
  </main>
    <section id="content">
        <article>
            <h2 class="post_title post_detail"><a href="https://www.ddkiss.com/archives/61.html" rel="bookmark"
                                                  title="Permalink to KMP算法之next数组求解说明">KMP算法之next数组求解说明</a></h2>

            <div class="post_list">
                <span>作者：</span><a href="https://www.ddkiss.com/author/bu-ding-yuan.html">布丁缘</a>
                <span class="post_category">分类：<a href="https://www.ddkiss.com/category/kai-fa-huan-jing.html" rel="bookmark"
                                               title="Permalink to 开发环境">开发环境</a></span>
                <span class="post_date">  时间：2017-10-13 16:32:00</span>

            </div>
            <div class="entry-content blog-post">
                <p>最近看了太多篇KMP算法的文章和书籍了，也只能是说理解了那段代码。网上有很多kmp算法的介绍，整个过程的推导都有。唯独对求解next数组，单独一篇博客能讲清楚的比较少，特别是能帮助初学者理解的不多。下面我来写下，哪些对我理解next求解过程有意义的博客。大部分内容来自引用。</p>
<h2>站在巨人的肩膀上</h2>
<p>下面由浅入深看下next数组如何求解</p>
<h3>1. 阮一峰的<a href="http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html">字符串匹配的 KMP 算法</a></h3>
<p>将整个匹配过程画出来了，方便直观理解kmp匹配过程。可惜，看完了图片你去看下代码？绝对让你一脸茫然。</p>
<h3>2. <a href="http://blog.csdn.net/v_july_v/article/details/7041827">从头到尾理解KMP</a></h3>
<p>朴素匹配算法时看过，文章看着挺累，没能坚持看完。不适合一上来就看，容易睡着。</p>
<h3>3. <a href="http://www.cnblogs.com/tangzhengyue/p/4315393.html">KMP算法的next数组详解</a></h3>
<p><img alt="kmp.png" src="https://www.ddkiss.com/usr/uploads/2017/10/3938395012.png"></p>
<p>这个图才让我真正明白<code>next[j]=k</code>中<code>next[j]</code>(距离)和<code>k</code>(索引)的真正含义。不懂的直接去看原文吧。需要注意的是有下面几点：</p>
<ol>
<li>求解next数组过程是已知 <code>next[j]=k</code>，求解<code>next[j+1]=?</code>的过程</li>
<li>初始条件<code>j =0; k =-1 ; next[j] = k</code>，理解距离如<code>A1=A2</code>和索引<code>k != j</code></li>
<li>只有<code>j</code>不断向前(+1)，<code>k</code>要么向前(+1),要么回溯(从0向右+?)</li>
<li><code>k</code>每次回溯的<strong>距离</strong>，取决于上一次计算的<code>next[k]</code></li>
<li>回溯时<code>k=next[k]</code>是将<strong>距离</strong>赋值给了一个<strong>索引值</strong></li>
<li>每次<code>s[j]=s[k]</code>，求解的是索引为<code>j+1</code>的next值。这样可以理解为何回溯的值可以从当前索引的next数组中获取。</li>
<li>从5中可以看出，如初始化时<code>j!=-1</code>，数组会越界。因为每次匹配是算下一字符的next数组值</li>
</ol>
<h3>4. <a href="https://61mon.com/index.php/archives/183/">KMP算法</a></h3>
<p>文章排版很清楚，但是next数组那段不如3中那张图那样让我顿悟了。不明白的可以都看看，没坏处。</p>
<h2>代码</h2>
<p>Java版的实现如下，可以对照着上面的说明看下。</p>
<table class="highlighttable"><tr><td class="linenos"><div class="linenodiv"><pre> 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42</pre></div></td><td class="code"><div class="highlight"><pre><span></span><span class="kd">public</span> <span class="kt">int</span><span class="o">[]</span> <span class="nf">getNext</span><span class="o">(</span><span class="n">String</span> <span class="n">pattern</span><span class="o">)</span> <span class="o">{</span>
    <span class="kt">int</span><span class="o">[]</span> <span class="n">next</span> <span class="o">=</span> <span class="k">new</span> <span class="kt">int</span><span class="o">[</span><span class="n">pattern</span><span class="o">.</span><span class="na">length</span><span class="o">()];</span>
    <span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="o">;</span>
    <span class="kt">int</span> <span class="n">j</span> <span class="o">=</span> <span class="o">-</span><span class="mi">1</span><span class="o">;</span>
    <span class="n">next</span><span class="o">[</span><span class="mi">0</span><span class="o">]</span> <span class="o">=</span> <span class="o">-</span><span class="mi">1</span><span class="o">;</span> <span class="c1">// next[i] == j</span>

    <span class="k">while</span> <span class="o">(</span><span class="n">i</span> <span class="o">&lt;</span> <span class="n">pattern</span><span class="o">.</span><span class="na">length</span><span class="o">()</span> <span class="o">-</span> <span class="mi">1</span><span class="o">)</span> <span class="o">{</span>
        <span class="k">if</span> <span class="o">(</span><span class="n">j</span> <span class="o">==</span> <span class="o">-</span><span class="mi">1</span> <span class="o">||</span> <span class="n">pattern</span><span class="o">.</span><span class="na">charAt</span><span class="o">(</span><span class="n">i</span><span class="o">)</span> <span class="o">==</span> <span class="n">pattern</span><span class="o">.</span><span class="na">charAt</span><span class="o">(</span><span class="n">j</span><span class="o">))</span> <span class="o">{</span>
            <span class="c1">//此时是已知next[i]，求解next[i+1]</span>
            <span class="c1">//此时j已经是通过next数组偏移后的值</span>
            <span class="c1">//next[i] == j 推导出 next[++i] = ++j;</span>
            <span class="n">next</span><span class="o">[++</span><span class="n">i</span><span class="o">]</span> <span class="o">=</span> <span class="o">++</span><span class="n">j</span><span class="o">;</span>
        <span class="o">}</span> <span class="k">else</span> <span class="o">{</span>
            <span class="c1">//j要回溯，那从0偏移next[j]长度位，索引是(next[j]-1)+1</span>
            <span class="n">j</span> <span class="o">=</span> <span class="n">next</span><span class="o">[</span><span class="n">j</span><span class="o">];</span><span class="c1">//利用已经算出的结果进行回溯</span>
        <span class="o">}</span>
    <span class="o">}</span>

    <span class="k">return</span> <span class="n">next</span><span class="o">;</span>
<span class="o">}</span>

<span class="kd">public</span> <span class="kt">int</span> <span class="nf">kmpMatch</span><span class="o">(</span><span class="n">String</span> <span class="n">source</span><span class="o">,</span> <span class="n">String</span> <span class="n">pattern</span><span class="o">)</span> <span class="o">{</span>
    <span class="kt">int</span><span class="o">[]</span> <span class="n">next</span> <span class="o">=</span> <span class="n">getNext</span><span class="o">(</span><span class="n">pattern</span><span class="o">);</span>

    <span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="o">;</span>
    <span class="kt">int</span> <span class="n">j</span> <span class="o">=</span> <span class="o">-</span><span class="mi">1</span><span class="o">;</span>

    <span class="k">while</span> <span class="o">(</span><span class="n">i</span> <span class="o">&lt;</span> <span class="n">source</span><span class="o">.</span><span class="na">length</span><span class="o">()</span> <span class="o">&amp;&amp;</span> <span class="n">j</span> <span class="o">&lt;</span> <span class="n">pattern</span><span class="o">.</span><span class="na">length</span><span class="o">())</span> <span class="o">{</span>
        <span class="k">if</span> <span class="o">(</span><span class="n">j</span> <span class="o">==</span> <span class="o">-</span><span class="mi">1</span> <span class="o">||</span> <span class="n">source</span><span class="o">.</span><span class="na">charAt</span><span class="o">(</span><span class="n">i</span><span class="o">)</span> <span class="o">==</span> <span class="n">pattern</span><span class="o">.</span><span class="na">charAt</span><span class="o">(</span><span class="n">j</span><span class="o">))</span> <span class="o">{</span>
            <span class="n">i</span><span class="o">++;</span>
            <span class="n">j</span><span class="o">++;</span>
        <span class="o">}</span> <span class="k">else</span> <span class="o">{</span>
            <span class="n">j</span> <span class="o">=</span> <span class="n">next</span><span class="o">[</span><span class="n">j</span><span class="o">];</span>
        <span class="o">}</span>
    <span class="o">}</span>

    <span class="k">if</span> <span class="o">(</span><span class="n">j</span> <span class="o">&gt;=</span> <span class="n">pattern</span><span class="o">.</span><span class="na">length</span><span class="o">())</span> <span class="o">{</span>
        <span class="k">return</span> <span class="n">i</span> <span class="o">-</span> <span class="n">j</span><span class="o">;</span>
    <span class="o">}</span> <span class="k">else</span> <span class="o">{</span>
        <span class="k">return</span> <span class="o">-</span><span class="mi">1</span><span class="o">;</span>
    <span class="o">}</span>
<span class="o">}</span>
</pre></div>
</td></tr></table>

<p><strong>注意：</strong>在<code>getNext</code>函数中数组边界可以有两种写法，都可以。
1.数组长度为<code>pattern.length</code>，循环时要减一<code>while (i &lt; pattern.length() - 1)</code>
2.数组长度为<code>pattern.length+1</code>，循环时<code>while(i&lt;pattern.length)</code>即可</p>
<h2>小结</h2>
<p>KMP算法中的递归计算next数组确实很赞。后来的人理解起来就没那么容易了。花了些时间，估计后面有时间会再来理解理解。就一遍，感觉理解不深。</p>
            </div>
            <div class="post_list">
              <div><span>Tags : </span>
              </div>
            </div>
        </article>
        <div id="container"></div>
        <script type="text/javascript" src="//dn-coding-net-public-file.qbox.me/Coding-Comments/v0.1.0/gitment.min.js"></script>
        <script>
            var gitment = new Gitment({
              owner: 'whusl',
              repo: 'BlogComments',
              oauth: {
                client_id: '621866266817529fba46681653017809',
                client_secret: '14188411740b12ae52159cee9b586bf85cd54125',
              },
            })
            document.getElementById('container').appendChild(gitment.render())
          </script>
    </section>
</article>

<!-- Footer -->
    <footer>
        <p> &copy;2017-2020&nbsp;<a href="http://www.miitbeian.gov.cn/" target="_blank">鄂ICP备17020200号</a>
          Blog powered by <a href="http://getpelican.com/">Pelican</a>
        </p>
    </footer>

    <!-- Analytics -->
    <script>
      var _hmt = _hmt || [];
      (function() {
        var hm = document.createElement("script");
        hm.src = "https://hm.baidu.com/hm.js?88c55edaf311dbacac56a16316b04c8b";
        var s = document.getElementsByTagName("script")[0];
        s.parentNode.insertBefore(hm, s);
      })();
    </script>

<script type="text/javascript">(function(){document.write(unescape('%3Cdiv id="bdcs"%3E%3C/div%3E'));var bdcs = document.createElement('script');bdcs.type = 'text/javascript';bdcs.async = true;bdcs.src = 'http://znsv.baidu.com/customer_search/api/js?sid=14490611060029767912' + '&plate_url=' + encodeURIComponent(window.location.href) + '&t=' + Math.ceil(new Date()/3600000);var s = document.getElementsByTagName('script')[0];s.parentNode.insertBefore(bdcs, s);})();</script>

</body>
</html>